home *** CD-ROM | disk | FTP | other *** search
/ Loadstar 237 / 237.d81 / t.making mazes < prev    next >
Text File  |  2022-08-26  |  3KB  |  122 lines
  1. u
  2.            M A Z E   M A N
  3.  
  4.       by Victor Terrana, Ph.D.
  5.  
  6.  
  7.     For the purpose of explaining the
  8. algorithm we should consider the
  9. screen to be covered by a rectangular
  10. grid. We will use coordinates to
  11. number the points in the grid
  12. starting with (1,1) in the upper left
  13. hand corner. The diagonal lines
  14. which form the walls and passages of
  15. the maze connect opposite corners of
  16. the squares of our grid. The points
  17. in the grid may be thought of as
  18. having even or odd parity according
  19. to the value of the sum of the two
  20. coordinates of that point.
  21.  
  22.  
  23.   (1,1)  (1,2)  (1,3)  (1,4)
  24.     .      .      .      .
  25.  
  26.  
  27.  
  28.   (2,1)  (2,2)  (2,3)  (2,4)
  29.     .      .      .      .
  30.  
  31.  
  32.  
  33.   (3,1)  (3,2)  (3,3)  (3,4)
  34.     .      .      .      .
  35.  
  36.  
  37.     The important fact here, and the
  38. secret to the construction of the
  39. maze is that the diagonal lines
  40. always connect points of the same
  41. parity, either odd to odd or even to
  42. even. For instance, the point (2,3)
  43. can be connected only to the four
  44. points (1,2), (1,4), (3,2) or (3,4).
  45. All of these points have the same
  46. (odd) parity.
  47.  
  48.     This principle of mathematical
  49. parity allows for a very simple
  50. method of maze construction.  We can
  51. form two (necessarily separate) wall
  52. sections, one connecting only points
  53. of odd parity and the other
  54. connecting only those with even
  55. parity. We position these two wall
  56. segments leaving spaces between the
  57. pairs of end points to act as the
  58. entrance and exit to the maze.
  59.  
  60.     The area confined by these two
  61. walls may now be filled at random with
  62. diagonal lines (and a few blank
  63. spaces).  It is impossible to cut off
  64. the entrance from the exit since this
  65. would involve a connection between one
  66. wall and the other consisting of
  67. diagonal lines. But these lines can
  68. never connect a point of odd parity
  69. (from one wall) with a point of even
  70. parity (from the other wall)! Thus, no
  71. matter how the interior of the maze is
  72. filled in with diagonal lines (between
  73. points in our grid) there will always
  74. be at least one path between the
  75. beginning and the end of the maze.
  76.  
  77.     The proportion of blank spaces
  78. used in the maze determines, to an
  79. extent, its complexity. If no spaces
  80. are used, the maze will consist of a
  81. single, long (but not very
  82. challenging) path from the entrance
  83. to the exit. Use of a few spaces
  84. allows for a choice of paths.
  85. However, many of these lead the maze
  86. tracer on a long journey back to
  87. where he/she started. The use of too
  88. many spaces creates several paths
  89. from entrance to exit and again may
  90. lead to a rather easy maze. The
  91. mazes formed by this program have
  92. about 5% blank spaces, a proportion
  93. which leads to fairly complex mazes
  94. without too many paths from beginning
  95. to end.
  96.  
  97.     Those readers who wish to try
  98. using the algorithm explained here in
  99. their own programs might want to
  100. consider a couple of alterations.
  101. The border of the maze can be made
  102. almost any shape as long as it
  103. consists of two pieces with opposite
  104. parity. You could create customized
  105. mazes using a special set of shapes.
  106.  
  107.     More traditional horizontal-
  108. vertical mazes can be constructed by
  109. using line segments two units long
  110. connecting either points with two even
  111. coordinates to each other or those
  112. with two odd coordinates. The
  113. remaining points in the grid become
  114. midpoints of these segments. In any
  115. case, Jeff and I both hope you enjoy
  116. the program we created from my
  117. algorithm.  Have fun!
  118.  
  119. Vic Terrana
  120.  
  121.  
  122.  
  123.